#include <fstream>
#include <iostream>
#include <deque>
#include <iomanip>
#include <sstream>
#include <string>
#include "tree_node.h"
using namespace std;

//struct BinaryTree {
//	BinaryTree *left, *right;
//	int data;
//	BinaryTree(int val) : left(NULL), right(NULL), data(val) { }
//};
//
//// Find the maximum height of the binary tree
//int maxHeight(BinaryTree *p) {
//	if (!p) return 0;
//	int leftHeight = maxHeight(p->left);
//	int rightHeight = maxHeight(p->right);
//	return (leftHeight > rightHeight) ? leftHeight + 1: rightHeight + 1;
//}

// Convert an integer value to string
string intToString(int val) {
	ostringstream ss;
	ss << val;
	return ss.str();
}
// Print the branches and node (eg, ___10___ )
void print_internal_nodes(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, 
						  const std::deque<std::shared_ptr<Node> >& nodesQueue, std::ostream& out) {
	std::deque<std::shared_ptr<Node> >::const_iterator iter = nodesQueue.begin();
	for (int i = 0; i < nodesInThisLevel; i++, iter++) {
		out << ((i == 0) ? setw(startLen) : setw(nodeSpaceLen)) << "" << ((*iter && (*iter)->left) ? setfill('_') : setfill(' '));
		out << setw(branchLen)  << "" << ( (*iter)?setfill('0'):setfill(' ') ) << setw(2) << ((*iter) ? intToString((*iter)->key) : "");
		out << ((*iter && (*iter)->right) ? setfill('_') : setfill(' ')) << setw(branchLen) << "" << setfill(' ');
	}
	out << endl;
}

// Print the arm branches (eg, /    \ ) on a line
void print_edges(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, 
				 const std::deque<std::shared_ptr<Node> >& nodesQueue, std::ostream& out) {
	std::deque<std::shared_ptr<Node> >::const_iterator iter = nodesQueue.begin();
	for (int i = 0; i < nodesInThisLevel; ++i, ++iter) {  
		out << ((i == 0) ? setw(startLen-1) : setw(nodeSpaceLen-2)) << "" << ((*iter)&&(*iter)->left ? "/" : " ");
		out << setw(2*branchLen+2) << "" << ((*iter)&&(*iter)->right ? "\\" : " ");
	}
	out << endl;
}


// Print the leaves only (just for the bottom row)
void print_leaves(int nodesInThisLevel, const deque<std::shared_ptr<Node> >& nodesQueue, std::ostream& out) {
	for (int i = 0; i < nodesInThisLevel; i++) {
		std::cout << std::setw(2) <<(nodesQueue[i] ? intToString(nodesQueue[i]->key) : "") << "  ";
	}
	out << std::endl;
}

void print_tree(const std::shared_ptr<Node>& root, std::ostream& out) {
	deque<std::shared_ptr<Node> > nodesQueue;
	nodesQueue.push_back(root);
	int n = 1;
	for ( int h = height(root); h > 0; --h, n*=2 ) {
		int branch_len = 2*(std::pow(2,h-1) - 1);  
		int node_interval_Len = 2*(std::pow(2, h) + 1); 
		int begin_len = branch_len + 2;
		print_internal_nodes(branch_len, node_interval_Len, begin_len, n, nodesQueue, out);
		print_edges(branch_len, node_interval_Len, begin_len, n, nodesQueue, out);

		for (int i = 0; i < n; i++) {
			std::shared_ptr<Node> currNode = nodesQueue.front();
			nodesQueue.pop_front();
			if (currNode) {
				nodesQueue.push_back(currNode->left);
				nodesQueue.push_back(currNode->right);
			} else {
				nodesQueue.push_back(nullptr);
				nodesQueue.push_back(nullptr);
			}
		}
	}
	print_leaves(n, nodesQueue, out);
}

void test_print_tree() {
	std::string str = "30 20 10 5 # # 15 # # 25 # 28 # # 40 35 # # 50 41 # # #";
	std::shared_ptr<Node> root = preorder_deserialize(str);
	std::cout << str << std::endl;
	std::cout << preorder_serialize(root) << std::endl;
	std::cout << bfs(root) << std::endl;
	std::cout << level_order_2queue(root) << std::endl;
	std::cout << level_order_1queue(root) << std::endl;
	std::cout << "height of the tree: " << height(root) << std::endl;
	std::cout << "height of the tree: " << bfs_height(root) << std::endl;
	cout << "Tree pretty print with level=1 and indentSpace=0\n\n";
	// Output to console
	print_tree(root, std::cout);
}